package com.cloud.code.算法.树;


import lombok.var;
import org.junit.Test;

public class BSTree<T extends Comparable <T> > {

    BSTNode<T> rootNode = null;

    static class BSTNode<T>{

        BSTNode<T> left = null;
        BSTNode<T> right = null;

        T data;

        public BSTNode(T data){
            this.data = data;
        }

    }


    public void add(T element){

        BSTNode<T> newNode = new BSTNode<>(element);

        if(rootNode == null){
            rootNode = newNode;
            return;
        }

        add(rootNode,newNode);
    }

    private void add(BSTNode<T> currentNode, BSTNode<T> newNode) {

        if(currentNode.data.compareTo(newNode.data) >= 0){
            if(currentNode.left == null){
                currentNode.left = newNode;
                return;
            }
            add(currentNode.left,newNode);
        }else {

            if(currentNode.right == null){
                currentNode.right = newNode;
                return;
            }

            add(currentNode.right,newNode);
        }


    }

    public void printTree(BSTNode rootNode){

        if(rootNode == null){
            return;
        }
        System.out.println(rootNode.data);
        printTree(rootNode.left);
        printTree(rootNode.right);

    }

    public int getHighTree(BSTNode rootNode){

        if(rootNode == null){
            return 0;
        }

        return Math.max(getHighTree(rootNode.left),getHighTree(rootNode.right))+1;
    }

    public void reverse(BSTNode rootNode){

        if(rootNode == null){
            return;
        }

        BSTNode left = rootNode.left;
        rootNode.left = rootNode.right;
        rootNode.right = left;

        reverse(rootNode.left);
        reverse(rootNode.right);

    }

    public BSTNode find(BSTNode<T> curNode,T element){

        if(curNode == null){
            return null;
        }

        if(curNode.data.equals(element)){
            return curNode;
        }

        if(curNode.data.compareTo(element) >= 0){
            return find(curNode.left,element);
        }else {
            return find(curNode.right,element);
        }
    }

    @Test
    public void test(){
        BSTree<Integer> bsTree = new BSTree<>();
        bsTree.add(5);
        bsTree.add(2);
        bsTree.add(1);
        bsTree.add(24);

        var printer = new TreePrinter();
        printer.print(bsTree.rootNode);

//        int highTree = bsTree.getHighTree(bsTree.rootNode);
//        System.out.println(highTree);
//
//        bsTree.reverse(bsTree.rootNode);
//        printer.print(bsTree.rootNode);

        BSTNode bstNode = bsTree.find(bsTree.rootNode, 1);

        System.out.println(bstNode.data);
    }


}
